package com.dylan.历史.算法;

import java.util.Stack;

/**
 * Created by Dylan on 2018/8/1.
 *
 * .编写一个类，用两个栈实现队列，支持队列的基本操作（add、poll、peek）
 */
public class 栈和队列1 {

    class TwoStackQueue {
        public Stack<String> stack1; // 用于加入元素的栈
        public Stack<String> stack2; // 用于获取元素的栈

        public TwoStackQueue() {
            stack1 = new Stack<>();
            stack2 = new Stack<>();
        }

        /**
         * 向队列增加一个元素,即向用于加入元素的栈压入一个元素
         */
        public void add(String word) {
            stack1.push(word);
        }

        /**
         * 获取并移除队列的头，如果队列为空，则返回null.
         * 如果用于获取元素的栈不为空,则从此栈中获取并移除元素
         * 如果用于获取元素的栈为空,则用于加入元素栈的所有元素都导入到用于获取元素的栈.再从用于加入元素的栈中获取并移除元素.
         * 如果用于加入元素的用于获取元素的栈都为空,则返回null.
         */
        public String poll() {
            if (!stack2.empty()) {
                return stack2.pop();
            }
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
            return stack2.empty() ? null : stack2.pop();
        }

        /**
         * 同理poll()
         */
        public String peek() {
            if (!stack2.empty()) {
                return stack2.peek();
            }
            while (!stack1.empty()) {
                stack2.push(stack1.pop());
            }
            return stack2.empty() ? null : stack2.peek();
        }
    }
}
